/**
 * 
 */
package array;

import java.util.Arrays;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael Given a sorted array, remove the duplicates in place such
 *         that each element appear only once and return the new length. Do not
 *         allocate extra space for another array, you must do this in place
 *         with constant memory. For example, Given input array A[] = [1,1,2],
 *         Your function should return length = 2, and A[] is now [1,2].］
 * @version 2013.1.12
 */
public class RemoveDuplicatesInPlace {

	// time O(nlogn), space O(n)
	public static int removeDuplicates4Sorted(int[] a) {
		assert (a != null);
		if (a.length == 0)
			return 0;
		Arrays.sort(a);

		int write = 0;
		int read = 1;
		for (read = 1; read < a.length; read++) {
			if (a[read] == a[write]) {
				continue;
			}
			a[++write] = a[read];
		}

		return write + 1;
	}

	public static int removeDuplicates4Unsorted(int[] a) {
		if (a == null || a.length <= 1) {
			return 0;
		}
		int write = 0;
		for (int fast = 1; fast < a.length; fast++) {
			int read;
			for (read = 0; read <= write; read++) {
				if (a[read] == a[fast]) {
					break;
				}
			}
			if (read > write) {
				a[++write] = a[fast];
			}
		}
		return write + 1;
	}

	public static int removeDuplicates4Unsorted1(int[] a) {
		if (a == null || a.length <= 1) {
			return 0;
		}

		int write = 0;
		for (int fast = 1; fast < a.length; fast++) {
			int read;
			for (read = 0; read <= write; read++) {
				if (a[read] == a[fast]) {
					break;
				}
			}
			if (read > write) {
				a[++write] = a[fast];
			}
		}

		return write + 1;
	}

	/**
	 * 
	 */
	public RemoveDuplicatesInPlace() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = CreateUtils.randNonNegIntArray(20, 10);
		// Arrays.sort(a);
		PrintUtils.printArray(a);
		int length = removeDuplicates4Unsorted1(a);
		for (int i = 0; i < length; i++)
			System.out.print(a[i] + " ");
	}

}
